// function quickSort(arr: number[], left: number, right: number) {
//     // 分区操作：将数组中的元素按照与基准元素的大小关系重新排列
//     function partition(arr: number[], left: number, right: number): number {
//         const pivot = arr[right]; // 通常选取右端元素作为基准
//         let i = left - 1; // 初始化小于基准的元素索引
//
//         for (let j = left; j < right; j++) {
//             if (arr[j] <= pivot) {
//                 i++; // 找到一个小于等于基准的元素，将其索引加一
//                 [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换元素位置，将较小元素移到前面
//             }
//         }
//
//         // 将基准元素放到正确的位置（所有左侧元素都小于它，右侧元素都大于等于它）
//         [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
//
//         return i + 1; // 返回基准元素的新位置（即分区点）
//     }
//
//     let index;
//     if (arr.length > 1) {
//         index = partition(arr, left, right);
//     if (left < index - 1) {
//       quickSort(arr, left, index - 1);
//     }
//     if (index < right) {
//       quickSort(arr, index, right);
//     }
//   }
//   return arr;
// }
//
// // 示例数据
// const unsortedArray = [5, 9, 2, 9, 1,122, 8, 3, 7];
//
// // 排序并输出结果
// const sortedArray = quickSort(unsortedArray);
// console.log(sortedArray);

